/**
 * 比较两个元素是否相等的函数类型声明。
 *
 * @template T 元素类型，默认为 unknown
 * @param older - 旧数组中的某元素
 * @param newer - 新数组中的某元素
 * @returns 如果两个元素相等，返回 true；否则返回 false。
 *
 * @example
 * const comparator: Comparator<number> = (a, b) => a === b;
 * comparator(1, 1); // true
 * comparator(1, 2); // false
 */
export type Comparator<T = unknown> = (older: T, newer: T) => boolean

interface DiffResult<T> {
  removed: T[]
  added: T[]
  matched: [T, T][]
}

const defaultComparator: Comparator = (older, newer) => older === newer

/**
 * 对比两个数组，找出被删除的元素、新增的元素以及（可选）匹配的元素对。
 *
 * @template T 元素类型
 * @param older - 旧数组（上一次的数据集）
 * @param newer - 新数组（当前的数据集）
 * @param comparator - 元素比较函数，用于判断两个元素是否相等。
 *                     默认使用严格相等（`a === b`）。
 *                     如果元素是对象，请提供按 `id` 或其他唯一键比较的函数。
 * @param absent - （可选）用于收集删除元素的数组，默认传入空数组。
 * @param additional - （可选）用于收集新增元素的数组，默认传入空数组。
 * @param identical - （可选）用于收集匹配到的元素对，形式为 `[oldItem, newItem]`。
 *                    若不需要收集匹配对，可省略此参数以提高性能。
 *
 * @returns 返回一个数组 `[absent, additional, identical?]`，其中：
 * - `absent` 是旧数组中有但新数组中没有的元素数组。
 * - `additional` 是新数组中有但旧数组中没有的元素数组。
 * - `identical`（可选）是匹配到的旧新元素对组成的数组。
 *
 * @example
 * // 基本类型数组比较
 * diff([1, 2, 3], [2, 3, 4])
 * // => [[1], [4], undefined]
 *
 * @example
 * // 对象数组比较（按 id）
 * const comparator = (a: { id: number }, b: { id: number }) => a.id === b.id;
 * diff(
 *   [{ id: 1 }, { id: 2 }],
 *   [{ id: 2 }, { id: 3 }],
 *   comparator
 * )
 * // => [[{ id: 1 }], [{ id: 3 }], [[{ id: 2 }, { id: 2 }]]]
 */
export default function diff<T>(
  older: T[],
  newer: T[],
  comparator: Comparator<T> = defaultComparator,
  absent: T[] = [],
  additional: T[] = [],
  identical?: [T, T][],
): [absent: T[], additional: T[], identical?: [T, T][]] {
  if (!older?.length) return [absent, newer, identical]
  if (!newer?.length) return [older, additional, identical]

  newer.forEach((newItem) => {
    const oldItem = older.find((o) => comparator(o, newItem))
    if (!oldItem) {
      additional.push(newItem)
    } else if (identical) {
      identical.push([oldItem, newItem])
    }
  })

  older.forEach((oldItem) => {
    const existsInNew = newer.find((n) => comparator(oldItem, n))
    if (!existsInNew) {
      absent.push(oldItem)
    }
  })

  return [absent, additional, identical]
}

/**
 * 比较两个数组，找出删除的元素、新增的元素，以及匹配的元素。
 *
 * @template T 元素类型
 * @param oldList - 旧数组
 * @param newList - 新数组
 * @param comparator - 比较函数，默认使用严格相等
 * @returns 对象，包含 removed、added 和 matched 数组
 */
export function diff2<T>(
  oldList: T[],
  newList: T[],
  comparator: Comparator<T> = (a, b) => a === b,
): DiffResult<T> {
  const removed: T[] = []
  const added: T[] = []
  const matched: [T, T][] = []

  if (!oldList?.length) {
    added.push(...newList)
    return { removed, added, matched }
  }
  if (!newList?.length) {
    removed.push(...oldList)
    return { removed, added, matched }
  }

  // 遍历 newList，找到新增的和匹配的
  let i = 0
  while (i < newList.length) {
    const newItem = newList[i]
    const oldItem = oldList.find((o) => comparator(o, newItem))
    if (!oldItem) {
      added.push(newItem)
    } else {
      matched.push([oldItem, newItem])
    }
    i++
  }

  // 遍历 oldList，找到移除的
  i = 0
  while (i < oldList.length) {
    const oldItem = oldList[i]
    const existsInNew = newList.find((n) => comparator(oldItem, n))
    if (!existsInNew) {
      removed.push(oldItem)
    }
    i++
  }

  return { removed, added, matched }
}
